﻿#define _CRT_SECURE_NO_WARNINGS 1
#include <stdio.h>
#include <stdlib.h>
#define p 1000005
#include <stdio.h>
int num[p];
int arr[p];
int main()
{
    int i, j;
    for (i = 2; i < p; i++)
    {
        num[i] = 1;
        arr[i] = 0;
    }

    for (i = 2; i < p; i++)
    {
        if (num[i])
        {
            for (j = 2; i * j < p; j++)
            {
                num[i * j] = 0;
            }
        }
    }
    //此时，所有值为1的num[i]中的i为素数
    for (i = 2; i < p; i++)
    {
        for (j = 2; i * j < p; j++)
        {
            if (i != j && num[i] == 1 && num[j] == 1)
            {
                arr[i * j] = 1;
            }
        }

    }

    for (i = 1; i < p; i++) {
        arr[i] = arr[i] + arr[i - 1];
    }//num[i]为从1到i的素数个数
    int a, b, n, temp;
    scanf("%d", &n);
    while (n--) {
        scanf("%d%d", &a, &b);
        if (a > b) {
            temp = a;
            a = b;
            b = temp;
        }
        printf("%d\n", arr[b] - arr[a - 1]);
    }
    return 0;
}
//题目描述
//如果一个合数x=p⋅q,p,q是素数且p≠q，我们称x是双素数。 现给你一个区间[a,b]，求区间内的的双素数个数。
//
//输入
//第一行是一个整数T(1≤T≤30000)，为样例的数目。 以后每行一个样例，为两个整数a,b(1≤a≤b≤106)
//
//输出
//依次每行输出一个样例的结果。
//
//样例输入
//3
//1 10
//1 100
//1 1000000
//样例输出
//2
//30
//209867
